// https://www.lintcode.com/problem/sort-integers/description

class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
     
   
    // selection sort I
    // void sortIntegers(vector<int> &A) {
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         for (int j = i; j < A.size(); ++j)
    //         {
    //             if (A[j] < A[i])
    //             {
    //                 int tmp = A[j];
    //                 A[j] = A[i];
    //                 A[i] = tmp;
    //             }
    //         }
    //     }
    // }
    
    // selection sort II
    // void sortIntegers(vector<int> &A) {
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         int min_idx = i;
    //         for (int j = i; j < A.size(); ++j)
    //         {
    //             if (A[j] < A[min_idx])
    //             {
    //               min_idx = j;
    //             }
    //         }
    //         int tmp = A[i];
    //         A[i] = A[min_idx];
    //         A[min_idx] = tmp;
    //     }
    // }
    
    // insertion sort
    // void sortIntegers(vector<int> &A) {
    //     for (int i = 0; i < A.size(); ++i)
    //     {
    //         int new_val = A[i];
    //         int j = i - 1;
    //         while (j >= 0 && A[j] > new_val)
    //         {
    //             A[j + 1] = A[j];
    //             j--;
    //         }
    //         A[j + 1] = new_val;
    //     }
    // }
    
    
    // bubble sort I
    // 注意冒泡排序的第一层循环是控制次数的，和选择排序思路不一样
//     void sortIntegers(vector<int> &A) {
//         if (A.empty()) return;
// // Input
// // []
// // Expected
// // []
//         for (int i = 0; i < A.size() - 1; ++i)
//         {
//             for (int j = 0; j < A.size() - 1; ++j)
//             {
//                 if (A[j] > A[j + 1])
//                 {
//                     // int tmp = A[j];
//                     // A[j] = A[j + 1];
//                     // A[j + 1] = tmp;
//                     swap(A[j], A[j + 1]);
//                 }
//             }
//         }
//     }
    
    // bubble sort II
    void sortIntegers(vector<int> &A) {
        if (A.empty()) return;
        while (true)
        {
            bool changed = false;
            for (int i = 0; i < A.size() - 1; ++i)
            {
                if (A[i + 1] < A[i])
                {
                    swap(A[i], A[i + 1]);
                    changed = true;
                }
            }
            if (!changed) break;
        }
    }
};